package com.lry.basic.algorithm.common;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/9/7
 */
//        给出一个区间的集合，请合并所有重叠的区间。
//        示例 1:
//        输入: [[1,3],[2,6],[8,10],[15,18]]
//        输出: [[1,6],[8,10],[15,18]]
//        解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
//        示例 2:
//        输入: [[1,4],[4,5]]
//        输出: [[1,5]]
//        解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
//  左 右
//A:1 3
//B:2 6
//区间合并条件：A的右>=B的左&&A的左<=B的右
public class MergePartition {
    public static void main(String[] args) {
        int[][]res = merge(new int[][]{{2,3},{4,5},{6,7},{1,8}});
        print(res);
    }
    public static int[][] merge(int[][] intervals) {
        if(null==intervals||intervals.length==0||intervals.length==1)return intervals;
        Arrays.sort(intervals,new Comparator<int[]>(){
            @Override
            public int compare(int[] a,int[] b){
                return a[0]-b[0];
            }
        });
        int al,ar,bl,br;
        List<int[]> resList = new ArrayList<>();
        for(int i=0;i<intervals.length-1;i++){
            al = intervals[i][0];//1
            ar = intervals[i][1];//3
            bl = intervals[i+1][0];//2
            br = intervals[i+1][1];//6
            if(hasPartition(al,ar,bl,br)){//重叠区间
                intervals[i+1][0]=Math.min(al,bl);
                intervals[i+1][1]=Math.max(ar,br);
            }else{//没有重叠区间加进去
                int[] res = new int[2];
                res[0]=al;
                res[1]=ar;
                resList.add(res);
            }
            //i<intervals.length-1导致最后一个没有加进去，这里加进去
            if(i==intervals.length-2){
                int[] res = new int[2];
                res[0]=intervals[i+1][0];
                res[1]=intervals[i+1][1];
                resList.add(res);
            }
        }
        return resList.toArray(new int[resList.size()][2]);
    }
    public static boolean hasPartition(int al,int ar,int bl,int br){
        return ar>=bl&&al<=br;
    }
    public static void print(int[][] img){
        for(int i=0;i<img.length;i++){
            for(int j=0;j<img[0].length;j++){
                System.out.print(img[i][j]+" ");
            }
            System.out.println();
        }
    }
}
